//给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
// 
//
// 示例 2： 
//
// 
//输入：head = [1], n = 1
//输出：[]
// 
//
// 示例 3： 
//
// 
//输入：head = [1,2], n = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中结点的数目为 sz 
// 1 <= sz <= 30 
// 0 <= Node.val <= 100 
// 1 <= n <= sz 
// 
//
// 
//
// 进阶：能尝试使用一趟扫描实现吗？ 
//
// 
//
// 注意：本题与主站 19 题相同： https://leetcode-cn.com/problems/remove-nth-node-from-end-
//of-list/ 
// Related Topics 链表 双指针 👍 31 👎 0

package leetcode.editor.cn;

class SLwz0R {
    public static void main(String[] args) {
        Solution solution = new SLwz0R().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    // Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        /**
         * 遍历两次，时间复杂度为O(n的平法)
         *
         * @param head
         * @param n
         * @return
         */
        /*
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (head.next == null && n == 1) {
                return null;
            }

            ListNode pre = head;
            int count = 1;  // 用来计数
            while (pre.next != null) {
                pre = pre.next;
                count++;
            }

            if (count == n) {
                return head.next;
            }

            // 循环到指定节点
            pre = head;
            for (int i = 0; i < count - n - 1; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;

            return head;
        }
        */

        /**
         * 双指针法
         * @param head
         * @param n
         * @return
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            // 使用虚拟头节点来处理头节点是否删除的问题
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;

            // 定义两个指针和一个临时指针赋值删除
            ListNode fast = dummyNode;
            ListNode slow = dummyNode;
            ListNode tmp = null;

            // 先将fast指针移动n个位置
            while (n-- > 0) {
                fast = fast.next;
            }

            // 此时fast和slow一起移动，当fast移动到尾部的时候，slow指针就是删除的节点
            while(fast != null) {
                tmp = slow;
                slow = slow.next;
                fast = fast.next;
            }

            // 删除该节点
            tmp.next = slow.next;

            return dummyNode.next;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
